package m202405.d22;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/22 18:18
 */
public class Q200 {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    find(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    //int[2]=>row-col
    private void find(char[][] grid, int row, int col) {
        Queue<Position> queue = new LinkedList<>();
        queue.add(new Position(row, col));
        while (!queue.isEmpty()) {
            Position position = queue.poll();
            if (grid[position.row][position.col] == '0') {
                continue;
            }
            grid[position.row][position.col] = '0';
            //上
            if (position.row > 0 && grid[position.row - 1][position.col] == '1') {
                queue.offer(new Position(position.row - 1, position.col));
            }
            //下
            if (position.row < grid.length - 1 && grid[position.row + 1][position.col] == '1') {
                queue.offer(new Position(position.row + 1, position.col));
            }
            //左
            if (position.col > 0 && grid[position.row][position.col - 1] == '1') {
                queue.offer(new Position(position.row, position.col - 1));
            }
            //右
            if (position.col < grid[row].length - 1 && grid[position.row][position.col + 1] == '1') {
                queue.offer(new Position(position.row, position.col + 1));
            }
        }
    }

    private static class Position {
        int row;
        int col;

        Position(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}
